class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        if (nums.size() == 0) return 0;

        int n = nums.size(), result = nums[0];
        vector<int> sums(n, 0);
        sums[0] = nums[0];

        for (int i = 1; i < n; i++) {
            sums[i] = max(sums[i - 1] + nums[i], nums[i]);
            result = max(result, sums[i]);
        }


        return result;
    }
};
